package main

import (
	"slices"
)

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	len1, len2 := len(nums1), len(nums2)
	sumLen := len1 + len2
	isDouble := (sumLen % 2) == 0

	//
	if len1 == 0 {
		if isDouble {
			return float64(nums2[len2/2]+nums2[len2/2-1]) / 2
		}
		return float64(nums2[len2/2])
	}

	if len2 == 0 {
		if isDouble {
			return float64(nums1[len1/2]+nums1[len1/2-1]) / 2
		}
		return float64(nums1[len1/2])
	}

	// medianIdx == idx1 + idx2
	medianIdx := (sumLen - 1) / 2
	idx1 := (len1 - 1) / 2
	L1, R1 := 0, len1-1
	idx2 := max(medianIdx-idx1, 0)
	idx2 = min(idx2, len2-1)
	old_idx1 := 0
	for {
		if idx2 == 0 {
			goto end
		}
		if nums1[idx1] < nums2[idx2] {
			L1 = min(idx1+1, len1-1)
		} else {
			R1 = max(idx1-1, 0)
		}
		old_idx1 = idx1
		idx1 = min(((L1 + R1) / 2), medianIdx)
		idx1 = max(idx1, 0)
		idx2 = max(medianIdx-idx1, 0)
		idx2 = min(idx2, len2-1)
		//
		if old_idx1 == idx1 {
			break
		}
	}

end:
	if isDouble {
		v1 := nums1[idx1]
		v2 := nums2[idx2]
		res_nums := []int{}
		if idx2-1 >= 0 && v1 < nums2[idx2-1] {
			res_nums = append(res_nums, v2, nums2[idx2-1])
		} else if idx1-1 >= 0 && v2 < nums1[idx1-1] {
			res_nums = append(res_nums, v1, nums1[idx1-1])
		} else {
			res_nums = append(res_nums, v1, v2)
		}

		slices.Sort(res_nums)
		return float64(res_nums[0]+res_nums[1]) / 2
	} else {
		if idx1 == len1-1 && nums1[idx1] < nums2[idx2-1] {
			return float64(nums2[idx2-1])
		}
		return float64(0)
	}
}

func main() {
	res := 0.0
	// res = findMedianSortedArrays([]int{2, 2}, []int{4, 4, 4, 4})
	// println(res)
	// res = findMedianSortedArrays([]int{4, 4, 4, 4}, []int{2, 2})
	// println(res)
	// res = findMedianSortedArrays([]int{2, 2, 4, 4}, []int{2, 2, 4, 4})
	// println(res)
	// res = findMedianSortedArrays([]int{1, 2, 3, 4, 5}, []int{6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17})
	// println(res)
	// res = findMedianSortedArrays([]int{2, 2, 4, 4}, []int{2, 2, 2, 4, 4})
	// println(res)
	// res = findMedianSortedArrays([]int{1, 3}, []int{2})
	// println(res)
	// res = findMedianSortedArrays([]int{1, 3}, []int{2, 4})
	// println(res)
	res = findMedianSortedArrays([]int{1, 2}, []int{3, 4})
	println(res)
}
